package leetcode;

/**
 * Created by Ghost on 2014/9/26 0026.
 */
public class Trapping_Rain_Water {
    public static int trap(int[] A) {
        if(A == null || A.length==0)
            return 0;
        int[] B = new int[A.length];
        int begin = 0;
        int end = A.length-1;

        int maxVal = A[begin];
        int maxIndex = begin;
        for(int i=maxIndex;i<=end;i++){
            if(A[i]>maxVal){
                maxIndex = i;
                maxVal = A[i];
            }
        }
        int i=begin+1;

        B[begin] = A[begin];
        while(i<maxIndex){
            int tmp = A[i-1];
            for(;A[i]<=tmp && i<maxIndex;i++)
                B[i] = tmp;
            B[i] = A[i];
            i++;
        }

        int j = end-1;
        B[end] = A[end];

        while(j>maxIndex){
            int tmp = A[j+1];
            for(;A[j]<=tmp && j>maxIndex;j--)
                B[j] = tmp;
            B[j] = A[j];
            j--;
        }

        if(i<=j){
            for(;i<=j;i++)
                B[i] = maxVal;
        }

        int result = 0;
        for(int ii=0;ii<A.length;ii++){
            result += (B[ii] - A[ii]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] A = new int[]{0};
        System.out.println(trap(A));
    }
}
